<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>合并排序</title>
  </head>

  <body>
    <script>
      /*
       * 合并排序（Merge sort），又叫归并排序，使用"分治法"的思想:把大问题拆分成小问题，解决小问题再合并成大问题；
       * 思路：将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

       * 例如：以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下
       * 1.将数组分成[3, 2, 4]和[5, 1]两部分。
       * 2.将[3, 2, 4]分成[3, 2]和[4]两部分。
       * 3.将[3, 2]分成[3]和[2]两部分，然后合并成[2, 3]。
       * 4.将[2, 3]和[4]合并成[2, 3, 4]。
       * 5.将[5, 1]分成[5]和[1]两部分，然后合并成[1, 5]。
       * 6.将[2, 3, 4]和[1, 5]合并成[1, 2, 3, 4, 5]。
       */

      function mergeSort(arr) {
        if (arr.length < 2) return arr;
        var middle = Math.floor(arr.length / 2);
        var left = arr.slice(0, middle);
        var right = arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
      }

      function merge(left, right) {
        var result = [];
        while (left.length && right.length) {
          if (left[0] <= right[0]) {
            result.push(left.shift());
          } else {
            result.push(right.shift());
          }
        }
        while (left.length) {
          result.push(left.shift());
        }
        while (right.length) {
          result.push(right.shift());
        }
        return result;
      }
      
      console.log(mergeSort([3, 2, 4, 5, 1]));
    </script>
  </body>
</html>
